package com.formula.datastructure.question.history;
// https://juejin.im/post/6844903831487152135

import com.formula.datastructure.util.DataUtil;

/**
 * 堆排序方法
 */
public class MaxK {
    Integer[] tree;
    int lastIdx;

    public MaxK() {
        tree = new Integer[20];
        lastIdx = -1;
    }

    public MaxK(int size) {
        tree = new Integer[size];
        lastIdx = -1;
    }

    public void add(Integer data) {
        tree[++lastIdx] = data;
        siftUp(lastIdx);
    }

    public Integer getTop() {
        return tree[0];
    }

    public Integer popTop() {
        Integer result = tree[0];
        tree[0] = tree[lastIdx];
        tree[lastIdx--] = null;
        siftDown(0);
        return result;
    }

    private void siftUp(int idx) {
        while (getParent(idx) >= 0) {
            if (tree[getParent(idx)] < tree[idx]) {
                Integer temp = tree[idx];
                tree[idx] = tree[getParent(idx)];
                tree[getParent(idx)] = temp;
            }
            idx = getParent(idx);
        }
    }

    private void siftDown(int idx) {
        while (getLeft(idx) <= lastIdx) {
            if (getRight(idx) <= lastIdx) {
                Integer temp = tree[idx];
                if (tree[getLeft(idx)] > tree[getRight(idx)]) {
                    tree[idx] = tree[getLeft(idx)];
                    tree[getLeft(idx)] = temp;
                    idx = getLeft(idx);
                } else {
                    tree[idx] = tree[getRight(idx)];
                    tree[getRight(idx)] = temp;
                    idx = getRight(idx);
                }
            }
        }
    }

    private int getParent(int idx) {
        if (idx == 0) {
            return -1;
        }
        return (idx - 1) / 2;
    }

    private int getLeft(int idx) {
        return 2 * idx + 1;
    }

    private int getRight(int idx) {
        return 2 * idx + 2;
    }

    public static void main(String[] args) {
        int size = 20;
        int range = 999;
        MaxK heap = new MaxK(size);
        Integer[] array = DataUtil.genUniqueArray(size, range);
        DataUtil.printArray(array);
        for (Integer data : array) {
            heap.add(data);
        }
        for (int i = 0; i < 6; i++) {
            System.out.println(heap.popTop());
        }
    }

}
